A pointer is a logical address in a program used to locate a particular data word within some region of memory. They are commonly used in many programming languages and allow powerful and elegant programs to be written. They can cause reductions in program execution speed because of the processing overhead. Because of the frequency with which pointer operations occur in program execution, it is critical to a processor's performance to handle them efficiently.
The program itself, plus any data which may be required during its execution by the processor, is stored in main memory. These regions of memory, or `segments`, may be contiguous (an `actual segment`) or divided into a number of `pages` for easier memory management (a `virtual segment`). A page is an actual segment of fixed size. Virtual or `paged` segments allow efficient use of the processor's memory resources, but again they can introduce a substantial overhead to maintain.
The presently described system involves an associative memory using ASDs or Actual Segment Descriptors which are sets of 4 words used to describe an actual segment of memory.
The system of virtual memory in which this ASDAM (Actual Segment Description Associative Memory) system occurs, is referred to as the ASD (Actual Segment Descriptor) system. It allows any individual word location in main memory to be referenced by identifying the region of contiguous memory wherein the word lies, plus the displacement of the word from the base of that region. The `ASD number` is the means of identifying a region of contiguous memory, when using the ASD system. Every region of contiguous memory has a unique ASD number, assigned by the operating system. The correspondence between the ASD number and the physical location of the region is provided by a table in main memory called the ASD table. An ASD number is 23 binary bits in length, limited by the amount of room in the pointers that have to contain them, while the displacement is 20 bits in length.
The purpose of the ASD system is to allow logical addressing, whereby programs referencing data can be written and compiled without knowledge of the physical address of the data in main memory. It is kept track of by the operating system. The ASD system of memory management allows data to be referenced throughout a region of memory much larger than that addressable using a 23 bit base address plus 20 bit displacement. This is done by using the ASD table to map the ASD number to a 32 bit base address.
The main memory is comprised of 48-bit words and these are grouped into actual segments, or contiguous regions. Each of these is given an ASD number. The ASD table stores, for each ASD number, the physical address of the beginning or `base` of the actual segment and various other information about the segment. The length of a page is 4096 data words in this system. A page table is an actual segment of memory which contains the ASD numbers of the various pages which comprise a given paged segment. The ASD number of the first page is at the first location, the second at the second location, etc. Every virtual segment has its own page table and it resides in memory. An example of a page table is shown in FIG. 2.
The ASD table stores information for every actual segment currently in use by the processor. It resides at a fixed location in main memory. The word containing the base address of a segment is referred to as the "ASD1" word. The ASD1 word of ASD number 0 is stored at memory address 0. For ASD number 1, it is stored at address 4, and so on for all ASD numbers. It may be seen that to translate an ASD number into the address of its ASD1 word, it is necessary to multiply the ASD number by 4. The ASD table is shown in FIG. 3.
A "pointer" may be considered to consist of three parts: An ASD number, a page index and a word index. The ASD number identifies a region of memory which may be paged or unpaged. The page index identifies, for a paged segment, which page is to be accessed. The word index indicates which word within the selected page contains the target data. In an unpaged pointer, i.e., a pointer which points to an unpaged segment, the ASD number is that of the segment containing the data. In a paged pointer, i.e., one that points to a paged segment, the ASD number is that of the virtual segment's page table.
The pointer is a "logical address" and before it can be used to access memory, it must be translated into a "physical address". This is done by identifying the base address of the actual segment containing the target data and adding to it the displacement given by the word index. Once this is done, the physical address is sent to main memory with a memory command requesting a read operation. This is referred to as a `Load`.
Here, the word "Load" refers to the placing of a data word (retrieved from memory) into the processor's register for purposes of executing a program.
A Content Addressable Memory (CAM) is a memory structure whose function is to indicate which of its internal data locations contains a data word presented to it as a `searchkey`. A data word is initially written into the CAM at a location indicated by an address input and thereafter, if the exact same data appears on the searchkey input, an indication of a match, called a `hit flag` is asserted and the `location number` of the data location containing the searchkey data is also provided as an output. The location number output of a CAM may be used as an address input to a RAM. The RAM then provides as an output, the data residing at the location corresponding to the location number of the original match in the CAM.
Without the use of the ASDAM system, "Loads" are achieved by a combination of hardware and microcode. The accessing of virtual segments can be a slow process and is "conventionally" achieved as follows:
The ASD number of the page table from the pointer is translated into the address of its ASD1 word, containing the base address of the virtual segment's page table. This is fetched from memory. The base address is added to the page index to form the address of the location in the page table which contains the ASD number of the particular page in which the required data resides. The ASD number at this address is then fetched from memory. This ASD number, when it returns, is translated into the address of its ASD1 word and a third memory request is issued to fetch this. The ASD1 word contains the base address of the page and the word index, (being the displacement from the base of the page) is added onto it. This finally is the address of the target word required. A fourth memory request is issued to fetch it. This process takes many machine cycles plus 4 serial memory accesses.
The ASDAM system described herein performs rapidly the otherwise tedious tasks of translating the logical address contained to reference main memory. In the best case, this entire operation may be achieved by the ASDAM in a single clock cycle.
The address translation is performed, when all data is present, by presenting the logical address (in pointer) to the ASDAM 8 (FIG. 1). Thus one CAM search and one RAM lookup provides the physical address in one machine cycle as later discussed in "case situation 1".